\section{Extracting Values from Sketch}
\label{app:extract}

For completeness, we give the pseudocode for extracting all the values stored in a quantile $\epsilon$-sketch in Algorithm~\ref{alg:extract}.

\begin{algorithm}[h]
\caption{ExtractValues($Q$, $n$)} 
\label{alg:extract}

{\bf Input:} Quantile $\epsilon$-sketch $Q$ of a stream of size $n$ 

{\bf Output:} $V = \{X_{i_1}, \ldots, X_{i_k}\}$, the set of values stored in the sketch

\begin{algorithmic}[1]
\STATE $V = \emptyset$
\FOR{$i = 0$ to $n$}
\STATE $v = $ result of querying $Q$ for the $i/n$ quantile
\STATE $V = V \cup \{v\}$
\ENDFOR
\STATE {\bf return} $V$
\end{algorithmic}
\end{algorithm}

Since, by definition, any quantile $\epsilon$-sketch returns only values that are in the stream, all the values returned must have been inserted into the sketch. Since the above algorithm computes all possible legal quantile values, its return value is the set of all values stored within the sketch. As shown earlier, if the $\{X_{i_j}\}$ are in sorted order, then $i_{j+1} - i_j \leq 2\epsilon n$. 

The main downside of this algorithm is that it takes $O(n)$ operations to extract all the values from the sketch. However, this part of the computation is not done during stream processing and is hence not as time-sensitive.

